package leecode.array.排序算法;

import java.util.Random;

/**
 * @author wangxi created on 2024/6/19 23:28
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/sort-an-array/
 */
public class QuickSort01 {


    private static final Random random = new Random();

    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return new int[0];
        }
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int partition = partition(nums, left, right);
        sort(nums, left, partition);
        sort(nums, partition + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        // 随机选取一下基准。否则会判题超时。因为存在3,2,2,2,2...2(n个2)，如果一直以left为基准，就会导致O(n*n)复杂度
        int index = left + random.nextInt(right - left + 1);   // 选取数组中任意一个元素，不包含边界
        // 把left的位置留出来，其他代码不变
        swap(nums, left, index);
        int key = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= key) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= key) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = key;
        return left;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
